//
// Created by chao.li on 2023/12/25.
//

#ifndef SOLUTIONS_SOLUTION032_H
#define SOLUTIONS_SOLUTION032_H
//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
//
//
//
//
//
// 示例 1：
//
//
//
//
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
//
//
// 示例 2：
//
//
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
//
//
// 示例 3：
//
//
//输入：s = ""
//输出：0
//
//
//
//
// 提示：
//
//
// 0 <= s.length <= 3 * 10⁴
// s[i] 为 '(' 或 ')'
//
//
// Related Topics 栈 字符串 动态规划 👍 2424 👎 0
#include <string>
#include <vector>
using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> indexStack;
        vector<char> charStack;

        vector<bool> notMatch;
        for(int i = 0; i < s.size(); ++i){
            if(charStack.empty()){
                indexStack.push_back(i);
                charStack.push_back(s[i]);
            } else{
                if(charStack.back() == '(' && s[i] == ')'){
                    indexStack.pop_back();
                    charStack.pop_back();
                } else {
                    indexStack.push_back(i);
                    charStack.push_back(s[i]);
                }
            }
        }

        notMatch.resize(s.length());
        while(!indexStack.empty()){
            auto index = indexStack.back();
            notMatch[index] = true;
            indexStack.pop_back();
        }

        int start = -1, end = 0, result = 0;

        while(end < notMatch.size()){
            if(!notMatch[end]){
                auto length = end - start;
                if(length > result){
                    result = length;
                }
            } else{
                start = end;
            }
            end++;
        }

        return result;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
#include <iostream>
void test(){

    string str = ")()())";
//    "(()"
//    ")()())"
//  "()"
    Solution s;
    auto list = s.longestValidParentheses(str);

    std::cout << (list);
}
#endif //SOLUTIONS_SOLUTION032_H
